The present invention is a system for natural language understanding which includes: a grammar processing method and a semantic processing method which converts natural language into previously stored experience and knowledge, natural language understanding based upon the previously stored experience and knowledge, a storage structure for storing experience and knowledge in a form which is convertible to and from natural language, and a method to add experience and knowledge from natural language input including problem solving.
The following references to prior art are made:
1. Bates, M. 1978. xe2x80x9cThe Theory and Practice of Augmented Transition Network Grammarsxe2x80x9d, L. Bolc (ed), NATURAL LANGUAGE COMMUNICATION WITH COMPUTERS. New York: Springer.
2. Cook, W. 1979. CASE GRAMMAR: DEVELOPMENT OF THE MATRIX MODEL. Washington D.C.: Georgetown University Press
3. Dyer, M. 1983. IN-DEPTH UNDERSTANDING. Cambridge, Mass.: MIT Press.
4. Earley, J. 1970. xe2x80x9cAn Efficient Context-Free Parsing Algorithmxe2x80x9d. COMMUNICATIONS OF THE ACM, Vol. 13, pp. 94-102.
5. Fillmore, C. 1968. xe2x80x9cThe Case for Casexe2x80x9d, in Bach, E., and Harms, R. (Eds), UNIVERSALS IN LINGUISTIC THEORY. New York: Holt, Rinehart, and Winston.
6. Guha, R. V., and Lenat, D. B. 1990. xe2x80x9cCyc: A Mid-Term Reportxe2x80x9d. AI Magazine, Vol. 11, No. 3, pp. 32-59.
7. Hendrix, G. G., Sacerdoti, E. D., Sagalowicz, D., and Slocum, J. 1978. xe2x80x9cDeveloping a Natural Language Interface to Complex Dataxe2x80x9d. ACM TRANSACTIONS ON DATABASE SYSTEMS Vol. 3, pp. 105-147.
8. Hirst, G. 1987. SEMANTIC INTERPRETATION AND RESOLUTION OF AMBIGUITY. Cambridge, England: Cambridge University Press.
9. Hutchins, S. 1991. xe2x80x9cSystem and Method for Natural Language Parsing by Initiating Processing Prior to Entry of Complete Sentencesxe2x80x9d, U.S. Pat. No. 4,994,966.
10. Lebowitz, M. 1988. xe2x80x9cThe Use of Memory in Text Processingxe2x80x9d. COMMUNICATIONS OF THE ACM, Vol. 31, pp. 1483-1502.
11. Kolodner, J. 1984. RETRIEVAL AND ORGANIZATIONAL STRATEGIES IN CONCEPT MEMORY. Hillsdale, N.J.: Lawrence Earlbaum
12. Kolodner, J. 1988. xe2x80x9cRetrieving Events from a Case Memory: A Parallel Implementationxe2x80x9d. Proceedings of the DARPA Workshop on Case-Based Reasoning, pp. 233-249. San Mateo, Calif.: Morgan Kaufmann.
13. Loatman, R., Post, D., Yang, C., and Hermansen, J. 1990. xe2x80x9cNatural Language Understanding Systemxe2x80x9d, U.S. Pat. No. 4,914,590.
14. Madron, T., xe2x80x9cExtracting Words form Natural Language Textxe2x80x9d, AI EXPERT, Vol. 4, No. 4, pp. 30-35.
15. Quirk, R., Greenbaum, S., Leech, G., and Svartvik, J. 1985. A COMPREHENSIVE GRAMMAR OF THE ENGLISH LANGUAGE. New York: Longman.
16. Sager, N. 1981. NATURAL LANGUAGE INFORMATION PROCESSING: A COMPUTER GRAMMAR OF ENGLISH AND ITS APPLICATIONS. Reading, Mass.: Addison-Wesley.
17. Schank, R., and Abelson, R. 1977. SCRIPTS, PLANS, GOALS, AND UNDERSTANDING. Hillsdale, N.J.: Lawrence Earlbaum
18. Schank, R., and Riesbeck, C. (ed), 1981. INSIDE COMPUTER UNDERSTANDING: FIVE PROGRAMS PLUS FIVE MINIATURES. Hillsdale, N.J.: Lawrence Earlbaum.
19. Schank, R. 1982. DYNAMIC MEMORY: A THEORY OF LEARNING IN COMPUTERS AND PEOPLE. Cambridge, England: Cambridge University Press.
20. Slade, S., 1991. xe2x80x9cCase-Based Reasoning: A Research Paradigmxe2x80x9d, AI MAGAZINE, (American Association of Artificial Intelligence) Vol. 12, No. 1, pp. 42-55.
21. Wilks, V., Huang, X., Fass. D., 1985. xe2x80x9cSyntax, Preference, and Right Attachmentxe2x80x9d, Proceedings of the Ninth IJCAI.
22. Winograd, T. 1983. LANGUAGE AS A COGNITIVE PROCESS. VOL. 1: SYNTAX. Reading, Mass.: Addison-Wesley.
23. Woods, W. 1970. xe2x80x9cTransition Network Grammars for Natural Language Analysisxe2x80x9d. COMMUNICATIONS OF THE ACM, Vol. 13, No. 10, pp. 591-606.
Previous work utilizing natural language processing has been in a few application areas: data base interfaces, translation, and understanding. The data base interfaces and translation work are similar in that the natural language input serves as a selector of an alternate representation. The natural language understanding work has been to classify natural language input sentences into possible defined categories for limited domains of categorization without any processing to determine if the categorization is consistent with natural language input sentences of the conversation. Other natural language processing work has expanded the limited categorization to fill in certain types of unstated information in a conversation for a limited situation and has included the capability of limited question answering about a conversation which has been categorized by this natural language processing. Still other natural language understanding work has stored and retrieved representations of specific natural language sentences, but this work lacks the capability of combining multiple natural language sentences into a representation of experience and knowledge.
The following describes the main references from the prior art. Discussion of various syntax processing methods is thoroughly described in Bates 1978, Sager 1981, Winograd 1983, and Hutchins 1991. Hutchins describes an efficient parser for detecting grammatical errors in natural language text. However, none of these parser descriptions utilize a grammar specification for both parsing incoming natural language and for forming natural language output. Quirk et al 1985 provide a thorough description of English grammar especially including the function of certain words such as pronouns, prepositions, conjunctions, interjections and other function words, prefixes and suffixes. Quirk et al also provides a detailed description of ellipsis, tense with related aspects, and clause formation and placement. However, this grammar description does not include a method for representing natural language nor does it include a method for selecting word senses of natural language words. Case frames are described in Fillmore 1968 and refined in Cook 1979. A method and apparatus for understanding natural language in the sense of selecting case frames which represent natural language text is disclosed in Loatman et al 1990. Case frames are a coarse categorization of natural language. Case frames lack the capability to represent the knowledge and experience implied from natural language in that case frames: have no representation for the implications of a case frame, have no representation for a process to realize the case frame, and have no capability to determine if the selected case frame is consistent with other case frames from the same natural language conversation. A limited representation of natural language is described in Schank 1977 and 1982. An instantiation of this representation is used to understand stories in terms of this limited representation, to match limited types of general experience, and answer limited questions about the understood story in Dyer 1983. A type of memory organization for storing and retrieving specific experience gained from understanding natural language using a type of Schank""s limited natural language representation is described in Kolodner 1984. Guha et al describes a memory system which stores knowledge in a two level data structure which are redundant. Each data structure is related to first order predicate calculus. This memory system heavily relies upon axioms which complicates the accessing of experience and knowledge related to a natural language conversation. Another complication is that this memory system utilizes natural language processing for a translation of natural language input to access the data structure related to first order predicate calculus. This memory system is not specifically designed for selecting word senses of natural language words.
This invention builds on the previous natural language understanding work and significantly expands the capabilities of the previous work. One expansion is to upgrade parsers: to efficiently handle ellipsis grammar and coordination grammar for understanding natural language; and to efficiently handle both parsing of incoming natural language and generation of outgoing natural language with the same syntax grammar data structures. Another expansion is to represent function words as functions. Function words include: certain adjectives, certain adverbs, pronouns, prepositions, and conjunctions. Function words have a wide range of processes which represent them. These processes define the function words, and are described in more detail in this section, and in the greatest detail in the preferred embodiment of this invention. Another expansion is to process morphological words, words with prefixes or suffixes, i.e., affixes. A Morphological word is processed into the phrase or clause or word senses and functions which represents the morphological word. Another expansion is to perform ellipsis processing to replace ellipted words, i.e., left out words, and then to perform processing which determines if the replaced words are consistent with the context of the conversation and stored experience and knowledge. Morphological words and ellipsis can be selectively utilized for text generated for outgoing communication from the invention.
Another expansion is to represent all non-function words with a meaning in terms of states and their values. An additional expansion is to assign the meaning of such words a word sense number. A word sense number is analogous to an address to a dictionary definition. However, the definition associated with a word sense number is in a form which allows: selecting a consistent and plausible definition, and hence its associated word sense number, from natural language; storing all that is known for the definition and all that is known to be related to the definition by realizing the definition with a state representation which is in terms of states, their values, and/or their relations; and structuring the definition and its associated word sense number for accessing the range of generality of what is known for the definition and of what is known to be related to the definition.
Another expansion is to combine the state representation of a natural language input, purposes, and the context of the conversation or the context of the situation into a three dimensional address which selects stored experience or knowledge in a memory of knowledge and experience. A purpose includes all related experience or knowledge such as: information content (information about an experience such as advantages), an activity (a set of actions), a plan, an intention, a causal path (a set of experiences related by cause), a result path (a set of actions related by accomplishing a result), or a goal. In general, a purpose has a purpose relation which is any concept which labels one clause or more than one related clause. The knowledge and experience in this memory are composed of data which represent natural language words, phrases, clauses, and groups of clauses. Each dimension can be assigned between a general value (unassigned) to a specific value (completely assigned). This range of dimension values selects experience or knowledge in a range of all that is stored for unspecified dimensions to all that meets a partial specification up to a specific experience or knowledge for a completely assigned specification. This range of specificness allows for natural language input to be understood in terms of previously stored experience and knowledge, and this further allows the natural language input to be then assigned a measure of plausibility and expectedness based upon previously stored experience and knowledge. Hence, an interpretation of a natural language input can be judged and reinterpreted when plausibility or expectedness criteria are not met. A particular application of the invention may make every plausible interpretation of a natural language input, and then the application can select the most plausible for example. Also, the accessing of experience and knowledge provides the capability to determine when new experience or knowledge is presented to the invention. This capability provides the first step in acquiring and understanding new experience and knowledge. Another aspect of the accessing of experience and knowledge is that when the invention encounters ambiguity or contradiction, the invention can generate a clarifying question for output. An application can also utilize the stored experience and knowledge related to its application to select a communication for output to incoming natural language statements to achieve the goals of the application. In general, an application can generate a communication for output.
An improved method and apparatus for understanding natural language in terms of stored experience is disclosed. This aspect of the invention is implemented with a syntactic method, followed by a phrase and clause state representation method, a purpose identification method, and an experience or knowledge retrieval method, a plausibility and expectedness check method, a context update method, and application specific ocesses including: further accesses of state representation memory and knowledge and experience memory, evaluation of application specific processes, and/or generation of outgoing natural language. The architecture of the memory system invention is summarized in FIG. 1.
The syntactic method includes steps of word isolation, dictionary look-up, function word processing, morphological processing, pattern recognition parsing, and ellipsis processing. The syntactic method is performed in a Natural Language Interface Processor 10 which is summarized in FIG. 2. Each natural language has its own natural language interface processor. Multiple natural languages can be processed to access a common state representation and a common experience and knowledge memory in one instance of the invention or in separate instances of the invention. An electronic form of text is input to the Text In Port 11 and is first processed by the Word Isolation Step 12 which identifies numerics, words, punctuation, and base words with inflections (e.g., a verb with the xe2x80x9cedxe2x80x9d inflection) or affixes. The Dictionary 20 stores words, and idioms which each have associated syntax wordsets and associated state representation addresses or function implementation addresses, and any grammar anomalies. Dictionary Look-Up Step 14 looks up the syntax wordsets which each input word belongs to and passes this information to the Parsing Step 16. Parsing Step 16 utilizes Memory 30 which contains syntax trees. These syntax trees are searched to identify the syntax usage of the Text In 11 words using syntax wordsets. The output of the Parsing Step 16 includes: phrases which include identifications of: function words, state representation words, modifiers, modifiees; the sentence role of phrase heads; and ellipsis identification. The syntax usage of each word is sent to the Dictionary Look-Up Step 18 which looks up addresses for state representation words and function word implementations.
The Function Word Processing Step 22 processes function words, affixes, and inflections including tense and related aspects. Function Word Processing Step 22 can select the function to be applied for single function words such as xe2x80x9caxe2x80x9d. Other function words cannot be processed until further processing of the input is performed such as xe2x80x9cthexe2x80x9d. Still others can be partially processed. For example, pronouns are tentatively replaced with a type and a pointer to a list of referents of that type starting with the latest referent of that type with the same case as the pronoun in the clause. These addresses point to the data structure associated with each word. The functions of function words have a general range of results including: adjectives defining specificity and group aspects of their noun modifiees; multiple function word adjectives implying combinations of functions for their noun modifiers, adverbs selecting word sense numbers of verbs, modifying state values, and setting and selecting aspects of processes which realize verb result states; pronouns which represent words either already in the context of a conversation, or words which are about to be communicated in the conversation; prepositions which relate aspects of meaning words, and which in some cases imply clause relations among words such as for prepositional phrases modifying adjectives; and conjunctions which combine words in a sentence role, such as the subject, and other conjunctions which imply the possible relations which a clause has to another clause.
Another part of the Dictionary Step 18 is to identify words which require morphological processing. The Morphological Processing Step 24 includes: identification of the group of functions associated with a morphological word""s base word, prefixes and suffixes; and the evaluation of one of these functions. Evaluation of the function results in a pointer to the address in the state representation data structure containing the base word plus affixes, or the function generates the state representation of the base word plus affixes as a phrase or clause. The generated phrase or clause contains representations of function words and state representation words. Words formed with a verb base (e.g., xe2x80x9csurprisinglyxe2x80x9d) often imply a clause for complete interpretation. The Ellipsis Processing Step 26 expands the ellipses identified in the Parsing Step 16 or the ellipsis related to morphological words. For example, general ellipsis has its source of text in the preceding natural language statements. Response ellipsis has its source of text determined by the response and the preceding sentence. Nonfinite verb (infinitive or participle) clauses can have ellipted elements. Nonfinite verb clauses with ellipsis are processed to replace the ellipted elements from specific sources in the sentence, the context, or state representation memory. Morphological state representations and ellipsis replacements for ellipted words are determined to be correct during subsequent state representation processing or purpose processing. If a clause is found to be inconsistent with respect to state representation or stored experience and knowledge, the morphological representation and/or ellipsis replacements are prime candidates for alternate representations or replacements.
The Adjective and State Abstract Noun Selector Method 50 operates in conjunction with the Concrete Noun State Representation Selector Method 60 to select the word sense number of adjectives modifying nouns. An adjective word sense number is composed of an identification number, a state value or value range, and an owner word sense number. The owner word sense number is typically a noun word sense number. The state representation of a state adjective is contained in Adjective and State Abstract Noun Representation Memory 80. A state representation entry in general contains the entry""s associated word sense number, pointers to verbs which set the state value if any, adverbial subclasses, which are used to select adverbial functions and which are described below, and pointers to purposes related to the state adjective in Experience and Knowledge Memory 150. 50 selects adjective word sense numbers which are compatible with its modifiers including adverbials and non-adverbial prepositional phrase modifiers. 50 processes adjectives with adverbials which require delayed evaluation. 50 also stores state values and their relations to entities in the conversation in Context Memory 120.
The Concrete Noun State Representation Selector Method 60 for concrete nouns selects a word sense number for each noun in a clause. A word sense number of a concrete noun selects a state representation in Concrete Noun State Memory 90. The word sense number of a concrete noun contains a word sense identifying number, a type number, a specificity number, and an experience number. The identifying number selects the representation of the general reference of a concrete which is all stored instances of that noun. The type number selects a type of the concrete noun. For example, xe2x80x9cfood storexe2x80x9d has the type of xe2x80x9cstorexe2x80x9d selected by xe2x80x9cfoodxe2x80x9d. The specificity number selects a partition of a type. For example, xe2x80x9cPolish food storexe2x80x9d has the specificness of the xe2x80x9cfood storexe2x80x9d selected by xe2x80x9cPolishxe2x80x9d. The experience number of a concrete noun selects a specific instance of the concrete noun. For example, xe2x80x9cPolonia""s Foodsxe2x80x9d is a specific instance of a (hypothetical) Polish food store. A zero type number, which implies a zero specificity and experience number, selects all types of the concrete noun. A zero specificity number, which implies a zero experience number, selects all specific types for a given type. A zero experience number selects all instances of a specific type of a concrete noun. A general concrete noun reference has zero type, specificity and experience numbers. A general concrete noun reference in a conversation is in general a composite of more specific references, called versions which comprise the possibly inconsistent descriptions of the general reference concrete noun in the conversation. A specific known reference has nonzero, type, specificity, and experience numbers. A specific unknown reference, i.e., a specific reference which is not specifically stored in Memory 90, has the type, specificity and experience number which best matches the specific unknown reference.
The state representation associated with a concrete noun word sense number is a set of states with a value or value range and a set of relations to other state representation words. Concrete noun state representations are stored in Concrete Noun State Representation Memory 90. A state and a value typically corresponds to a natural language adjective. Noun relations include relations to other nouns such as A-Relations, i.e., Associative relations which include: possessive, partitive, function, which are clausal relations, and group relations. Other noun relations include C-Relations, i.e. Comparison relations, S-Relations, i.e. State relations, and T-Relations, i.e. Transfer relations. A C-Relation is a comparison between a state value at the C-Relation to another state value. An S-Relation transfers a state value from a source, usually a modifier, to a destination, usually a modifiee. A T-Relation transfers multiple state values. An example of a T-Relation is a modifier which sets the type number of a noun modifiee. A-, S-, and T-Relations can be implied by direct modification of a noun by a noun, a morphological word modifying a noun, or a prepositional phrase modifying a noun. C-Relations are implied by function words indicating a comparison to another state representation word. A concrete noun""s state representation in Memory 90 contains pointers to states in Memory 80, and pointers to descriptors of A-, C-, S-, and T-descriptors. These descriptors contain information which includes participants in the relation and values of relations. Relations can also have pointers to other relations including clauses.
The state representation of a concrete noun is organized hierarchically in order to help select the word sense number of a specific unknown noun or of a version of a general reference noun. The hierarchical organization is realized by associating state values and modifier relations with word sense numbers hierarchically. The state representation of a concrete noun contains pointers to super-types (i.e. parents) and subtypes (i.e. children). The state values which are common to most instances of a type or specificity number are only listed with the most general word sense number. For example, xe2x80x9cbasketball playerxe2x80x9d has xe2x80x9ctallxe2x80x9d associated with the zero specificity number state representation. However, if a specificity number has a different value for the xe2x80x9cheightxe2x80x9d state, such as xe2x80x9cgrammar school basketball playerxe2x80x9d, the appropriate state value is stored with the specificity number and zero experience number. Also, a specific instance, which has a non-zero experience number, has the xe2x80x9cheightxe2x80x9d state value which is correct for the individual. Other types of modifiers are handled in the same manner as adjectives. The state representation data structures of this invention not only stores the state representation, but these structures also contain organizations or data which aids in selecting word sense numbers.
Selector 60 selects word sense numbers of concrete nouns. This method first determines if a reference is a re-reference to a concrete noun. A re-reference does not require further processing. A new reference which is a non-modifying sentence role is first processed by Selector 70, a method which selects verb word sense numbers. 70 selects word sense numbers for noun phrase heads which are subjects, and objects which are compatible with a word sense number of the verb. The possible word sense numbers of a noun phrase head are stored in Dictionary 20. These noun word sense numbers selected by 70 are the most general word sense numbers which are compatible with the verb word sense number. 70 also assigns a requirement set of states, conditions, and/or relations which the selected word sense number must not change because changing these requirements would invalidate the selected word sense numbers. The requirement set is another example of a data structure component which is utilized for word sense number selection. After the processing at 70, a noun phrase head is processed for its modifiers. Modifier word sense numbers are selected to maintain the word sense number requirements of the noun phrase head if possible. Modifier word sense number selection is complicated by the multiple possible modifiees of a modifier in noun phrases with more than one premodifier or more than one prepositional phrase. If a modifiee is not compatible with a modifier, an alternate modifiee is selected if possible. Another complication of noun phrase modifiers is that coordinated modifiers can imply multiple noun phrase heads as in xe2x80x9cwood and aluminum batsxe2x80x9d. Another complication of noun phrase modifiers is that relations between nouns in certain cases are modified by adverbials. Also, the modifiers could be elliptical or morphological, in which case, the modifier may require alternate elliptical or morphological processing. 60 also sets the type of referent for a concrete noun. The type of referents are: specific known, specific unknown, specified general (represented by word sense numbers with version numbers), and unspecified general (zero type, specificity, and experience numbers). In addition to selecting the word sense numbers of the constituents of a noun phrase including prepositional phrase modifiers, 60 processes word sense number selection for: coordinated noun modifiers and noun phrase heads, noun and adjective subject complements, prepositional complements for adverbial and adjective modifiers, and non-morphological abstract nouns.
Abstract nouns which are a state of an owner, such as xe2x80x9chealthxe2x80x9d, are called state abstract nouns. The word sense number of a state abstract noun is a combination of a state adjective word sense number and a concrete noun word sense number. A state abstract noun word sense number has an identification number which includes a state value or value range and an owner word sense number, which are components of a state adjective word sense number. In addition, a state abstract noun word sense number contains a type number, a specificity number, and an experience number, components of a concrete noun. A state abstract noun has a data structure in Concrete Noun State Representation Memory 90 which is similar, but somewhat specialized, to a state abstract noun state representation. The main specialization for a state abstract noun is a pointer to a state representation data structure in Adjective and State Abstract Noun Representation Memory 80. State abstract nouns are selected by Selector 60 in conjunction with Selector 50. The word sense number of a state abstract noun is selected in a method which is similar to concrete nouns. Modifiers of state abstract nouns including function words and adjectives often times select the state value of the abstract noun""s state or indicate ownership of the state. For example xe2x80x9cgoodxe2x80x9d modifying xe2x80x9chealthxe2x80x9d sets a state value while xe2x80x9chisxe2x80x9d modifying xe2x80x9chealthxe2x80x9d indicates ownership of the state.
Another type of abstract noun has a word sense number characterized by a clause such as xe2x80x9ccluexe2x80x9d. This type of abstract noun is called a clausal abstract noun. Typically, the characterizing clause describes the criteria required by an instance of the corresponding abstract noun""s state representation. For example, one characterizing clause for xe2x80x9ccluexe2x80x9d is: xe2x80x9cSomething that helps to solve a homework problem.xe2x80x9d A clausal abstract noun has a specialization of the state representation of a concrete noun in Concrete Noun State Representation Memory 90. The word sense number of a state abstract noun contains an identification number, a type number, a specificity number, and an experience number which are essentially the same as the equivalent in a concrete noun word sense number. The clausal abstract noun has a pointer in 90 to its representation in Clausal Abstract Noun and Clausal State Representation Memory 100. Another specialization for a clausal abstract noun is that 90 may contain pointers for certain modifiers of the clausal abstract noun that point to modifiees other than the clausal abstract noun. These other modifiees are usually in the characterizing clause. Clausal abstract noun state representations are selected by Concrete Noun Selector 60. A component of the word sense selection of a clausal abstract noun is to select some or all of the sentence role referents in the characterizing clauses. The state abstract noun referent, called the representational referent, is typically selected. A referent is found by utilizing categories of referents which are contained in group A-descriptors associated with the referent. A direct category contains word sense numbers which are matched with word sense numbers in Context Memory 120 to select a referent. An indirect category contains noun and adjective word sense numbers which are requirements to be met by a word sense number in 120 to select a referent. If no match from the context is found, a general referent is assumed for the unmatched sentence roles. Adjectives modifying such abstract nouns which did not have a stored modification in the state abstract noun""s representation in Memory 90 are converted to adverbs by adding suffixes if possible by the Morphological Processing Step 24, and these generated adverbs are checked to determine if they modify the verb in the clause.
At this point in the Selector 50 and Selector 60 method, concrete nouns and their modifiers, and non-morphological abstract nouns have been replaced with pointers to their state representations which include all that is known about the state of the concrete nouns including state values just set by modifiers and state values already set before and stored in the context. Prior to the processing of concrete nouns and non-morphological state abstract nouns, non-state representation words and implied functions have been selected and evaluated except for certain functions which have delayed evaluation. Pronouns have also been tentatively replaced with a pointer to a referent in the context. Other function words have had their function selected and evaluated. Ellipted elements have been replaced. Morphological words have been processed. Nonfinite verb phrases and morphological words implying clauses have also been processed.
The next step is to perform the Clausal Abstract Noun and Clausal State Representation Selector 70 method. During the processing of concrete noun and non-morphological abstract noun phrases which are non-modifying sentence roles, i.e., main sentence roles, Selector 70 selected word sense numbers for such sentence roles, i.e., subjects, indirect objects, and direct objects. 70 also selected a word sense number for the verb which is compatible with the main sentence role nouns. The selection of these word sense numbers comprise the first phase of the verb word sense number selection. The first phase selection process is complicated by coordinated main sentence role constituents. One complication is that multiple verb word sense numbers may have to be selected because the multiple constituents imply multiple verb word sense numbers for a single verb, and thus imply multiple separate clauses. Another complication is that certain constituents actually are special usages such that such a constituent is not semantically intended to perform its sentence role. For example, xe2x80x9cMary and her baby went shopping.xe2x80x9d really means xe2x80x9cMary went shopping with her baby.xe2x80x9d In this example, the xe2x80x9cbabyxe2x80x9d did not go xe2x80x9cshoppingxe2x80x9d, but instead the xe2x80x9cbabyxe2x80x9d accompanied xe2x80x9cMaryxe2x80x9d.
The verb word sense number selected in the first phase is only partially selected in the first phase. A verb word sense number contains an identification number which defines the verb word sense number, and includes partial to complete word sense identification numbers of main sentence roles. The verb identification number(s) are selected in the first phase. The verb word sense number also contains a type number, specificity number, and experience number. The type number selects a set of processes which are purposes which describe the realization of the verb""s result state. A process or other type of purpose is said to realize process or purpose in the sense that the set of clauses associated with a process or purpose are added to the context which is the same as stating the clauses of the process or purpose. Stating clauses makes them real (assuming the clauses are true) with respect to the present invention. In general, a verb process is a set of clauses which accomplish the result states associated with a verb. The result state of a verb is a set of states and values associated with the affected sentence role element or other entity. The state representation of a verb is stored in Clausal Abstract Noun and Clause State Representation Memory 100 for a verb word sense number. FIG. 19b contains the process independent format for the data of a state representation and includes: the result states and values for each affected entity, pointers to the word sense number""s pointers in Clausal Abstract Noun and Clause Purpose Memory 130, a pointer to shared adverbial data structures, a pointer to the typical process of the verb word sense number in Experience and Knowledge Memory 150, and a list of adverbial data structures which select processes of the verb word sense number. FIG. 19d contains the format for the requirements of main sentence roles to perform the typical process of the verb word sense number. FIG. 19e depicts the format for adverbial data structure elements which are specific to a verb word sense number. FIG. 19e contains the format for the state representation of a verb word sense number which includes the process type, specificity, and experience numbers. This format includes: specific requirements of main sentence roles beyond the typical process requirements to perform the process associated with a verb word sense number; joint/separate criteria for multiple constituent sentence roles; a list of adverbial data structure elements which are specific to the verb word sense number including adverbials which are required for the process to be performable; and a pointer to the process associated with the word sense number in Memory 130.
The phase 1 verb word sense number selection method creates requirements for all possible word sense numbers of a stated verb. In the processing of main sentence roles at Selector 60 for concrete nouns for sentence roles with coordinated constituents, it is possible that different constituents require different verb word sense numbers. The phase 2 verb word sense number selection method first determines which constituents must form separate clauses for different word sense numbers, and forms separate clauses as needed.
The phase 2 process also processes the stated adverbials modifying the verb in a clause under process. The function associated with an adverbial is selected by matching an adverbial subclass which is possible for a verb with a possible adverbial subclass associated with the adverbial. An adverbial modifying a verb can be a function word, a morphological word or a prepositional phrase in English for example. A clause can also grammatically act like an adverbial, but such a clause adverbial is processed as a clause. A verb""s or other modifiee""s adverbial subclass contains a semantic role, and source requirements for the adverbial modifier which includes a function, a general or verb specific set of parameters. An adverb""s subclass contains a semantic role, a source requirement for the adverbial modifier, a destination requirement for the modifiee, and a function which realizes the effect of the adverbial upon the modifiee of the adverbial. A modifiee""s adverbial subclass matches a modifying adverbial subclass if the semantic roles match and the source requirements and destination requirements are met. The range of semantic roles are broadly: time, space, process, modality, (point of) reference, purpose. Broadly, the function is to set some aspect of the verb""s word sense number such as: setting semantic role parameters, selecting a word sense number of the verb, selecting or modifying an aspect of a process which achieves the verb""s word sense number, modifying the resulting states of the verb""s word sense number, and/or commenting about the verb""s word sense number. Applying the function to the modifiee realizes the modifying effect of the adverbial upon the modifiee of the adverbial. An adverbial can possibly have more than one adverbial subclass which matches the verb""s or other modifiee""s adverbial subclasses. The most likely adverbial subclass of an adverbial is selected by ordering the adverbial subclasses in the most recently used first in the context order. The most likely adverbial was most recently stated in the conversation. Processing a prepositional phrase adverbial typically requires evaluation of noun prepositional complements at Selector 60. The 70 method also processes coordinated adverbials which may imply separate clauses. Clause adverbials are set up for purpose processing. The processing of adverbials modifying other parts of speech utilizes the adverbial selection method of 70.
The phase 2 verb word sense number selection method also optionally selects the possible processes of the verb word sense number. The possible processes are selected by matching additional requirements and checking for the status of required adverbials in the clause or in Context Memory 120. Such required adverbials may not be explicitly stated in the clause, but instead are contained in the context. Each process can have joint/separate criteria which is utilized to determine if a clause with multiple constituents joined with a conjunction implying joint sentence role membership actually requires separate clauses. For example, xe2x80x9candxe2x80x9d can imply joint sentence role membership. Separate clauses could occur for example when a process requires the subjects to be at the same location, but actually the subjects are at different locations. Each possible process of a verb word sense number in a clause with such coordinated main sentence role constituents is set with a joint/separate status indicator.
The Selector 70 method also evaluates mood for verbs. Other processes of the 70 method include: coordinating the conversion of adjectives to adverbials, and determining the adverbial subclass including function evaluation for certain modifiers of clausal abstract nouns and certain modifiers of adjectives modified by non-adverbial prepositions; and determining the aspects of a source clause of a clausal T-Relation that are to be transferred to the destination clause of the clausal T-Relation. This Selector 70 method is for state setting verbs. Relation verbs such as xe2x80x9cto bexe2x80x9d, xe2x80x9cto havexe2x80x9d (in the sense of xe2x80x9cto possessxe2x80x9d) have the relation selected by Selector 60.
After the verb word sense number of a clause has been completely processed at 70, the next step is to perform the Purpose Identifier 140 method. This method utilizes the clausal state representation. This method attempts to find a purpose relation with the current clause and the clauses and states in the context of the conversation, and in this way performs discourse analysis. Associated with the state representation of a clause are the set of purposes which that clause can be related to. Each purpose has pointers to the preceding and succeeding clauses which are within or related to the purpose. A state and a value can also be related to a purpose. Thus, a clause with a relation setting verb can also be related to a purpose when such verbs indicate a state value relation. Also, stored noun relations can also have associated clauses with purposes. The associated clauses contain information for the relation. Thus, any clause can potentially have a purpose. A noun relation has an associated clause pointer to the clause stored in Concrete Noun State Representation Memory 90. A clause has a pointer to its purposes in Clausal Abstract Noun and Clause Purpose Memory 130. A state and a value or value range has a pointer to its purposes in Adjective and State Abstract Noun Purposes Memory 110. FIG. 21b contains the format for a purpose node entry. An entry contains the owner word sense number, i.e., adjective, abstract noun, or verb. The entry also contains the purposes associated with the word sense number. The purposes are organized by the type of purpose, i.e., the purpose""s function such as consequence. Each purpose has a purpose address and a pointer to a purpose realization entry in Memories 110 or 130.
A purpose address, illustrated in FIG. 21a, contains an identifier and category information. The purpose""s identifier contains a location component and a function component. The location component is the address of the purpose node table and entry number in Memories 110 or 130. The function component indicates the information or relation contained in the purpose. The purpose can contain a function descriptor purpose which can be a word, phrase, or one or more clauses. The function descriptor purpose describes the function at the level of detail appropriate for the application. The category information of a purpose includes a path type number, a path specificity number, and an experience number. A path type number is associated with all paths of the purpose realization in Memory 150 which end in a common leaf node. A path specificity number is associated with path that has at least one unique sub-path among the purpose addresses with a common path type number. An experience number is associated with a specific path in Memory 150.
A purpose node entry, as illustrated in FIG. 21b, have purpose addresses organized by function with an associated relative frequency for the purpose address in that function. Also, a purpose address in a purpose node entry has a pointer to a purpose realization entry, as depicted in FIG. 21c. A purpose realization entry has a data structure which stores the purpose node entries which own the purpose realization entry, i.e. purpose node entries which have pointers to the purpose realization entry. The purpose realization entry contains purpose addresses of purposes related to the purposes owning the purpose realization entry. These purposes are categorized by function including: processes which realize the owning purpose""s clause, consequence purposes of the owning purpose, motivation purposes of the owning purpose, and other types of purposes specific to a particular purpose. The other purposes include: advantages, disadvantages, alternatives, qualities, etc. Finally a purpose realization entry has a pointer to the purpose realization entry""s Experience and Knowledge Memory 150 entry which is illustrated in FIG. 21d. The Memory 150 entry contains: the address of its purpose realization entry address in Memory 110 or 130; Memory 150 addresses of preceding entries of the current entry and access conditions for each preceding entry which must be satisfied for the preceding entry to possibly precede the current entry; Memory 150 addresses of concurrent entries of the current entry and access conditions for each concurrent entry; Memory 150 addresses of succeeding entries of the current entry and access conditions for each succeeding entry; and information related to the preceding, concurrent, and succeeding Memory 150 addresses.
The entries in Memory 150 define a directed graph of nodes. A node has an associated purpose, and a node has an associated natural language clause. A path of a purpose in the directed graph has a set of nodes and associated clauses which describe the purpose associated with the nodes on the path. The clauses of a path is said to realize a purpose. The clauses in a path which realize a purpose have a common purpose relation. A purpose relation is any concept that labels one clause or more than one related clause. For example, a purpose for setting computer operating system parameters contains the clauses that describe the settings and how to set them. A clause in a conversation is related to stored experienced and knowledge by finding a purpose of the clause which is common to the purpose of one or more other stated or implied clauses in the conversation, and by finding a path of Memory 150 nodes which have satisfied access conditions with the values for satisfying conditions stored in Context Memory 120 from the natural language statements of the conversation. If a value or data for a condition is not stored in 120, the application of the invention determines if the condition with the missing value is satisfied according to the goals of the application. A purpose path can have a purpose address for a stored purpose realization, or a purpose path can have a new combination of clauses which realize a new purpose realization. To summarize, a clause has an associated purpose node entry. A purpose node entry has purpose addresses of the clause with associated addresses of a purpose realization entry for each purpose address. A purpose realization has related purpose addresses and a pointer to a Memory 150 entry which corresponds to a node of a directed graph. The nodes on a path in the directed graph and the nodes"" associated natural language clauses realize a purpose through description of the purpose. A realized purpose is feasible, or assumed to be feasible, for the context of the conversation. Feasibility is assumed for hypothetical or predicted situations for example. Thus, an instantiation of a purpose can be determined by the states of a context or situation.
Clauses are represented by word sense numbers of verbs, adjectives, or abstract nouns in Experience and Knowledge Memory 150. Verb word sense numbers are directly convertible into natural language clauses. A characterizing clause associated with a clausal abstract noun is also directly convertible into a natural language clause. Clauses of adjectives are realized with the owner of the adjective as a subject with the adjective as a subject complement such as: xe2x80x9cJohn is sick.xe2x80x9d State abstract nouns are expressed as the owner of the state abstract noun, a form of xe2x80x9cto havexe2x80x9d with a xe2x80x9cto possessxe2x80x9d word sense and the state abstract noun such as: xe2x80x9cJohn has good health.xe2x80x9d Nouns and relations between nouns can have associated clauses which belong to purpose paths in Memory 150. Thus, all types of state representation words can have related experience and knowledge in Memory 150.
The REL-SELECT method of the Purpose Identifier 140 first searches for a match of the current clause""s related purposes with a purpose established in the conversation. A purpose is established if it has two or more stated clauses on its purpose path, or if the purpose identifier function is stated. The purpose addresses in the purpose node of the current clause are checked for matching the established purposes in the conversation. After established purposes are checked for, purposes between the current clause and application dependent other clauses in the conversation are checked for. The method also invokes a classifying purpose, a special type of purpose stored in Memory 150 and described below, which determines a possible purpose relation of the current clause. Multiple classifying clauses can be invoked. Sometimes a related purpose is not found. A related purpose would not be found for a new purpose which is being added to the conversation for example. If the REL-SELECT method fails to select any purpose relation, the clause is set to a default description purpose.
A clause with a default description process is temporarily accepted as a correct interpretation. The Communication Manager determines when alternatives related to a default description purpose are to be performed depending upon the application and the status of the application. For example, in subsequent conversation, the clause with a default description purpose will either become related to the conversation or not. If this clause does not become related, this clause is assumed to be an aside, i.e. a clause which is not directly related to the conversation. If it becomes related to the conversation, this clause""s purpose will also be determined through its relation to the conversation. Also, if no related and consistent purpose is found for a clause, one or more of several other alternatives can be performed for example depending upon the application and the status of the application: reinterpret the current clause by either looking for an alternate possible clause implying word sense number or by reinterpreting the sentence role with the lowest confidence level, wait for a situation dependent number of sentences for the anomaly of no known purpose to be explained and then failing to get an explanationxe2x80x94issue a clarifying question, accept the clause interpretation if the current clause meets expectedness and plausibility criteria in the context of the conversation and assume the current clause is a new topic or an aside (a clause unrelated to the conversation), assume the clause is related by random occurrence in time for certain situations, or immediately issue a clarifying question. The selection of the alternative depends upon the application and the status of the application.
If REL-SELECT finds a stored purpose relation or a stored purpose relation is designated between the current clause and other clauses of the conversation, a feasible purpose path is optionally searched for in Memory 150 by the PATH-FIND method of Purpose Identifier 140. PATH-FIND attempts to find a purpose path between the current clause and the other clause in the conversation of the stored purpose relation. An application of the invention may utilize more than one of the found purpose relations be processed for finding a path. The correct direction between the current clause""s node and the other clause""s node is selected. Nodes in that direction which have satisfied access conditions, and possibly satisfy application specific conditions, are kept in the search. The search continues until the other node is reached, or all possible paths have failed. In this case, another possible purpose found by REL-SELECT or another designated purpose relation is processed with the same method. The PATH-FIND retraces the search upon the failure of a node to satisfy its access conditions or other conditions. The PATH-FIND method searches for all feasible paths of a purpose concurrently. The concurrent search of multiple paths has the advantage of eliminating the need to determine which paths have been checked, and nodes which fail to satisfy access conditions can be used to prune other paths which include such a node in their paths.
The PATH-FIND method also searches for processes to realize a verb word sense number, and searches for paths which realize state value changes for states. PATH-FIND is further generalized to allow the stopping of its method upon the failure to satisfy a node""s access conditions or other application dependent conditions. In this case the application can decide how to proceed. This stopping is useful for solving problems which are similar to previously solved problems which have been stored in Memory 150. Upon failure at a node under this situation, the application can attempt to determine how to proceed with the new problem so as to use part of the previously solved problems. This stopping is also useful for gathering which conditions have to be overcome for a proposed purpose path. If PATH-FIND fails to find a feasible path, the alternatives are similar to the options for the default purpose relation of REL-FIND.
The PURPOSE-MANAGER is another method of Purpose Identifier 140. The PURPOSE-MANAGER controls the activation of REL-SELECT and PATH-FIND for an application. The PURPOSE-MANAGER also activates Plausibility and Expectedness Checker 170 which is described below. Other tasks of the PURPOSE-MANAGER include: computing time relations of a clause to the conversation, processing the computation of a clause""s modal which implies the truth value of the clause, interfacing with the application for determining the application""s communication with respect to the current clause or with respect to the application, and generating a data structure which contains the knowledge and experience which is used to generate natural language for output such as the application""s communications.
Classification purposes are a special stored type of purpose in Experience and Knowledge Memory 150. A classification purpose has paths in Memory 150 which are used to classify an object associated with a particular classification purpose. The first node of a classification purpose contains access conditions which are satisfied to reach the next node. Paths are traced for a classification purpose with PATH-FIND. PATH-FIND traces paths until all paths have no succeeding nodes or all paths have failed to meet access conditions. PATH-FIND utilizes another type of ending or failing node method for classification purposes which stores the failing or ending node without retrace. Each ending path has an associated classification component of the object. The classification components are combined to form the classification. For example a classification purpose which classifies the association of a purpose to a clause determines if the state representation of a clause and knowledge and experience related to the clause satisfy access conditions which determine if the clause can be associated with the function of the purpose. The utility of classification purposes for associating purposes is that they are a compact method for characterizing purposes compared to storing numerous paths of purposes obtained from experience. For example, the set of questions asked by a student seeking a tutorial can be varied in content and order. A classification purpose can determine what additional communications beyond answering a student""s questions will help the student learn the knowledge. A general advantage of classification purposes over other decision methods is that classification purposes can be formed through natural language description through an application of the invention.
Dynamic Purposes are another special stored type of purpose in Experience and Knowledge Memory 150. A dynamic purpose has a set of purpose paths which are traced concurrently by satisfying access conditions as other types of purposes. Dynamic Purposes differ from other types of purposes in that certain ending nodes have associated processes which are executed when the node is accessed. An example of a possible dynamic purpose application is the process which would implement driving a car. There are various purpose activities such as: accelerating, braking, lane changing, turning, etc. A dynamic purpose for driving a car would trace paths as conditions change. When an ending node is reached, its associated process would be performed. Dynamic purposes can be used to control interactions during the execution of an application of the invention. Another use of dynamic purposes for the invention is to utilize dynamic purposes to select and apply sub-purposes which implement problem solving activities. Another use of dynamic purposes for the invention is to partially implement the Communication Manager 160 (CM). The CM initializes the invention for communication, handles errors or exceptions, and manages text output and other forms of outgoing communication. The CM controls communication from optional application processes of the invention including for example applications that: manage storage of experience and knowledge; control access to experience, knowledge and methods; have special purposes for answering/asking questions about meaning of words; store requests needing special authorization; and similar executive functions. The CM is partially implemented with dynamic purposes.
A plausibility and expectedness check method is performed by the Plausibility and Expectedness Checker 170 in conjunction with the storage or retrieval of experience or knowledge. Each time the state representation of a clause is accessed for the first time, the Plausibility and Expectedness Checker 170 is optionally activated by the PURPOSE-MANAGER. The plausibility check determines if the clause and purpose path linking it to the conversation is likely or not. The expectedness check determines if the clause and purpose path is stored in the invention""s state representation memories, and experience and knowledge memory. Plausibility is measured by the benefits of the doer(s), i.e., the performer, of the clause and the benefits to the receiver(s), i.e., the owners, of the result states set by the clause. The benefits are estimated with stored knowledge and experience organized into a classification purpose. Other plausibility measures are specific to the application of the invention.
Expectedness is partially based upon the relative frequency stored from previous experience. The relative frequency is the number of times the interpreted clause has occurred divided by the number of times all alternative clauses including the interpreted clause have occurred. The alternative clauses represent the experience or knowledge which has previously been stored for the same context or the most similar context. The alternative clauses can have their relative frequencies calculated based upon experience, or the relative frequencies can be assigned permanently, or the assigned relative frequencies can be updated through experience. The expectedness of the constituents of the clause are also measured. The expectedness measure has a value range between expected and unexpected. A clause which has been previously stored, and which is consistent with the context of the conversation and previously stored experience or knowledge is expected. The unexpectedness measure of an access are the components of the clause and the components of the related purposes of the clause which have not been previously stored. A non-extreme expectedness value is calculated by measuring the number of matches for qualifying criteria which are applicable for the clause and for the purposes in knowledge and experience memory. A criterion can contribute an equal value of expectedness or each criterion can have a specific value of expectedness. An overall combination of expectedness and plausibility is calculated utilizing equal or varying weights for each component of plausibility and expectedness. This combined value is then compared to a threshold value associated with an application. If the combined value exceeds the threshold, the interpretation is accepted. If the plausibility check falls below a threshold or the expectedness check fails, the checker communicates with the Communication Manager 160. Then depending upon the application, the Communication Manager activates dynamic purposes which select for example one or more of the following alternatives: selecting a sentence role to be reinterpreted and invoking the selector which interprets the sentence role; wait for a situation dependent number of sentences for the anomaly to be explained and then failing to get an explanationxe2x80x94issue a clarifying question; immediately issue a clarifying question. The selection of the alternative depends upon the application and the status of the application.
The Context Memory Controller 125 method is performed upon the Context Memory 120 after a clause has been understood in terms of stored experience and knowledge. The Context Memory Controller 125 is invoked by the Communication Manager. The state representation of nouns in the clause are updated including relations to other nouns in the context and they are stored in Context Memory 120. This includes whether the noun is specific and is known or unknown or is general. Also, other lists are maintained by Controller 125 to aid in selecting a pronoun referent. The state representation of the clause including word sense numbers is also stored. The relation of the clause to the other clauses including the purpose path is stored. Associated with each clausal state representation is a descriptor which includes a stated or implied modal, and a source. Modals indicate the status of a clause and include adverbials and auxiliary verbs such as xe2x80x9ccanxe2x80x9d. The modal function is associated with the modal. The source values include: stated, implied, assumed, hypothesized, deduced, calculated, application specific, etc. Lists of sentence role participants are stored and associated with clauses. These lists are used in pronoun referent selection and purpose identification methods. Adverbial lists are maintained to aid adverbial subclass selection.
After a clause has been processed for state representation including word sense selection, processed for purpose relation and path selection, and processed for plausibility and expectedness, and had its context stored, the next step is to perform the storage or retrieval of experience or knowledge from the Experience and Knowledge Memory 150. The application, Purpose Identifier 140, or the Communication Manager 160 retrieve experience or knowledge from Memory 150. For example, after identifying a purpose of a just interpreted clause, if the application requires it, the Purpose Identifier 140 generates retrievals from Memory 150 of at least the state representation of the clauses on the path connecting the current clause to the conversation. These retrieval accesses are performed to ensure that inconsistencies, impossible state values, implausible clauses, implausible states, or unavailable entities are not required to relate the new clause to the conversation through the connecting path. The Purpose Identifier 140 can select the process to achieve the state change of state setting verbs or the selection of the process to achieve the relation between sentence roles for relation verbs depending upon the application and the status of the application. For example, an application which requires separating factual input from fallacious input can have this goal achieved by verifying that the understood clauses could at least be accomplished based upon stored experience and the context. Another application might require the process to meet some objective such as the quickest process. Such a requirement would mean all available processes be checked. Additional accesses could also be performed for applications which require that all possible state representations of a clause be considered. Under this requirement, all consistent combinations of main sentence role word sense numbers are selected. If more than one verb word sense number is found, additional accesses are required to find the interpretation which is best related to the conversation. Still further additional accesses may be needed when one or more purposes on an identified purpose path contradicts a statement in the conversation. Under this situation the Purpose Identifier 140 finds a new purpose path to replace the contradicted path. If none can be found, a clarifying question can be issued through the Communication Manager 160 for example.
Other additional accesses may be required depending upon the application and the content of the clause. For example, if the application is tutoring and the clause is an answer to an exercise, the additional retrievals would occur to determine if the student""s answer is correct and acceptable with additional retrievals to diagnose an incorrect answer. If the answer is correct, additional retrievals would be made to perform the next operation of the tutoring. This example illustrates a different type of Memory 150 access: accessing 150 to select a communication for incoming natural language statements. An application can utilize any known technical method to select a communication including utilizing Memory 150. One utilization of 150 to select a communication is to store communication related purposes in a clauses purpose realization entry. A communication related purpose could be: a purpose that realizes a communication, a purpose with paths that describe the difference between incoming natural language statements and the goals of the application, a classification purpose which selects a communication, a classification purpose which classifies the type of communication, a dynamic purpose which invokes processes to generate a communication, etc. The application can then utilize the Purpose Identifier 140 method to select a communication or set up application specific methods that select a communication. It is possible that no communication would be selected. Also, a communication could be delayed until the end of a sentence, or the completion of a user input for example.
Once a communication has been selected by an application or by one or methods of the invention, the next step to be performed is to generate an output. This step is typically performed after all the steps of an application of the invention have been performed for an input including all additional accesses and method executions associated with an application beyond the understanding method. The output can be a natural language statement. Alternately, the output can be audible, symbolic or graphical for example, and an output is communicated through the Non-Textual Natural Language Interface 40. The symbolic or graphical output represents the equivalent of a natural language statement. The natural language output is formed by the application selecting clauses from the purpose path(s) for example. These purpose paths have been selected by the additional processing of the application. The application selected clauses are chosen to incorporate the level of detail and explanation which matches the application and status of the application.
The application must select the sentence role referents for the selected clauses of an output communication. Associated with each node of a purpose in Memory 150 is a representation of a state or clause which is associated with that purpose. The state representation of the clause on the selected purpose path is converted into natural language by instantiating the sentence roles with the corresponding entities from the Context Memory 120 and/or the sentence role referents associated with a clause and its associated purpose in Memory 80 or 100. The stored sentence role referents of clauses in Memory 150 would be utilized for example for such circumstances as: adding new generalized sentence roles to the conversation, bringing specific new references into the conversation, and/or recalling previous specific or generalized references related to the conversation or situation. Some sentence role referents are from the context in Memory 120 for sentence roles which are specific to the conversation or situation for example. The source of the referents is selected by the application to convey the desired information as determined by the application.
The Communication Manager 160 sends the clauses selected by the application to Text Generation Step 200. The method of converting a set of clauses into natural language utilizes the parsing data structure which is also utilized for parsing incoming natural language. Text Output Step 200 is a method of Natural Language Processor 10. The tense and related aspects of the verb are set by the application, application status, and/or output content. Function words are derived from or stored with the experience or knowledge to be output from Memories 80, 90, 100, 110, 120, 130 or 150. The first step of 200 is to utilize a classification process to select clauses which are to be combined into a sentence for clauses have certain purpose relations. Next the main sentence roles of a clause in the sentence are processed. A sentence role already in the context is processed for realization with ellipsis or a pronoun by a classification purpose. Some sentence roles are designated or required to be realized as morphological words.
The realization of nouns is particularly complicated because of the theoretically unlimited levels of modifiers modifying modifiers in a noun phrase and the restriction of the allowed realization types of modifiers modifying their modifiee. For example, certain modifier to modifiee relations require that the modifier be realized as a prepositional phrase. In order for a noun phrase to be realized as a single noun phrase, the modifiees between the prepositional phrase and the noun phrase head must also be realized as prepositional phrases. If such a modifiee can not be realized as a prepositional phrase, the noun phrase must be expressed as more than one noun phrase. Adverbials modifying verbs can be realized in general as function words, morphological words, or prepositional phrases. There are often multiple positions for placement of an adverbial modifying a verb phrase. Certain combinations of morphologically realized adverbials are not stylistically acceptable, and require either different realizations or different position placement if possible. Adverbials realized as prepositional phrases uses the noun phrase generation of Text Generation Step 200. Adjective phrases utilize both the adverbial generation method and noun phrase generation method of 200. The modifiers of nouns, verbs, and adjectives may require morphological processing. Coordinated phrases of main sentence role heads and coordinated modifiers are generated as needed. Ellipsis processing including coordination ellipsis and pronoun replacement is also applied to formed main sentence role phrases, formed clauses, and formed sentences. Finally, as phrases are generated, punctuation is added as required.
Text Generation 200 sends an electronic text form to the Text Out Port 28 which is connected to a computer system, a video display terminal, a computer program, other computer system apparatus, or electronic apparatus. If the output is to be audible, symbolic or graphical for example, the elements of the clause are translated into the form needed to generate the audio, symbol or graphic element by the Non-Textual Natural Language Interface 40. This translation is performed by looking up the output representation associated with a state or clause representation. Then the associated output function of the computer system such as a video display terminal or external computer program is activated with the output information associated with the output representation. Also, the output representation from Interface 40 can include any form of non-textual natural language equivalent generated from natural language text.
It is an object of this invention to provide a new and improved natural language syntax processing method for separating incoming natural language into each word""s sentence role and for selecting the order of words for generating outgoing natural language text utilizing the same syntax data for both methods.
It is an object of this invention to provide a new and improved method for selecting the function and in some cases, the associated relation, of all natural language function words for a natural language.
It is an object of this invention to provide a new and improved method for processing a morphological word of a natural language into the state representation associated with the morphological word. This state representation includes function words, the word sense number of the base word, and the word sense number of other state representation words from the context or stored information.
It is an object of this invention to provide a new and improved method for replacing the ellipted words in a natural language statement with their intended replacement from the context or stored information.
It is an object of this invention to provide a new and improved memory system for storing the state representations of adjectives, concrete nouns, clausal abstract nouns, state abstract nouns, and verbs.
It is an object of this invention to provide a new and improved method for organizing and accessing the state representation of a word with a word sense number.
It is an object of this invention to provide a new and improved method for selecting the word sense numbers of concrete nouns, of state abstract nouns, of clausal abstract nouns, and of their state representation word modifiers which is consistent with the state representation of these nouns, with the state representation of their modifiers, with the relations between these words and their modifiers, and with the context of the conversation.
It is an object of this invention to provide a new and improved method for selecting the word sense numbers of state representation word adjectives and of their state representation word modifiers which is consistent with the state representation of these adjectives, with the state representation of their modifiers, with the relations between these words and their modifiers, and with the context of the conversation.
It is an object of this invention to provide a new and improved method for selecting the word sense numbers of state representation word verbs and of their state representation word modifiers which is consistent with the state representation of these verbs, with the state representation of their modifiers, with the relations between these words and their modifiers, with the word sense numbers of the other main sentence role word sense numbers, and with the context of the conversation.
In accordance with these and other objects, it is a further aspect of this invention to perform the selection of verb word sense numbers upon the clauses in a sentence with multiple clauses in an order which simplifies processing of a cataphoric pronoun, i.e., a referent stated in the future of the conversation. The clauses are processed in left to right order. A clause containing clauses in sentence roles is processed after the sentence role clauses are processed.
It is an object of this invention to provide a new and improved method for selecting the purpose relations of a clause which are related to the context of the conversation or situation containing the clause.
It is a further aspect of this invention to use conjunctions including adverbial conjunctions to simplify the selection of purpose relations of a clause by utilizing conjunctions. A conjunction relating clauses can select or limit the possible selections of the relationship of two clauses joined by a conjunction. Certain usages of clauses with ellipsis such as nonfinite verb clauses can also have limited purpose relations.
It is an object of this invention to provide a new and improved method for selecting the paths of clauses comprising experience and knowledge which connect a clause with the clauses in the context of the conversation or situation containing the clause.
It is a further object of this invention to generalize the selecting the paths of clauses to include: paths of clauses which are processes to realize the result state values of a clause, paths of clauses which are processes to realize the state value change of a state, a method to utilize classification purposes which classify an object by finding paths of clauses, a method to utilize dynamic processes which select a process or method by finding paths of clauses, and a method to utilize an application method to select a path continuation when one is missing.
It is an object of this invention to provide a new and improved method for organizing and accessing purpose relations with purpose addresses.
It is an object of this invention to store the context of the conversation in a memory system. This memory system contains the following information from the conversation: the word sense numbers of state representation words and certain related function word addresses, the word sense numbers or function address of their modifiers, purpose relations between clauses including timing and modality of the clauses, paths, a categorization of state representation words for selecting pronoun referents, and adverbial subclasses.
In accordance with these and other objects of this invention, it is a further object of this invention to provide a new and improved memory system for storing and retrieving experience and knowledge with the word sense number of the state representation of natural language clauses and with the paths which are related to the context of a conversation or situation. The accessing of this memory system is improved because it contains experience and knowledge which is compactly represented by word sense numbers. The memory system provides for a robust access by using a representation of natural language words which are relevant to an application in terms of states and/or functions represented by word sense numbers and function codes. This representation allows for an understanding of natural language input which is consistent with the context, and previous experience and knowledge. Also, this representation is not limited to a set of primitives. Instead, all experience and knowledge is represented at the level of detail at which it has been experienced. Further experience and knowledge can increase the level of detail of experience and knowledge, or further experience and knowledge can combine previously unrelated experience and knowledge in a generalization. Still further experience and knowledge can indicate conditions under which certain experience and knowledge is selected to be more applicable than other experience and knowledge.
It is another object of this invention to provide a new and improved method and apparatus for storing and retrieving experience and knowledge with an address with multiple dimensions and a flexible assignment of dimensional components. One dimension, the word sense number of the state representation of an natural language clause or a part thereof, can represent a specific, general, or partial instantiation. A specific instantiation represents one experience or knowledge unit. A general instantiation represents all experiences or knowledge units, A partial instantiation represents a subdivision of a general instantiation.
It is a further aspect of this invention to have a second dimension for storing or retrieving experience or knowledge which is related to purpose relations expressed or derived from a natural language conversation or a described situation. This second dimension is a purpose address. A purpose address contains an identifier and category information. The category information organizes purpose relations into: a general partition, i.e., all related purpose relations, a partition by designating certain requirements, i.e., purpose paths which have one or more unique subpaths, and a single purpose path, i.e., a purpose which represent one experience or knowledge unit, and thus have a single path.
It is a further aspect of this invention to have a third dimension for storing or retrieving experience or knowledge. This third dimension is the context of one or more related conversations or one or more situations. The context stores the location of the state representation of the conversation including word sense numbers, explicit, implied and assumed experience and knowledge and other information as described for the context storage object of this invention. The context is utilized for selecting the word sense numbers of the state representation, purpose relations, and purpose paths. When a context is not specified, as at the beginning of a conversation, context is built by the conversation, and the context is general. For a general context, all components utilized to make a selection are selected from related state representations and/or experience and knowledge in the most likely first order or by an application specific method. If the context has not been completely specified for a selection, the unspecified component is selected from related state representations and/or experience and knowledge in the most likely first order or by an application specific method. This selected, unspecified component is utilized for the selection. If the component is specified, the specified context components are utilized in the selection.
In accordance with these and other objects of this invention, a method is provided to store and retrieve all experience and knowledge which is expressible in natural language and which is selected for storage in the memory system of the invention by utilizing the specific/general/partial flexibility of assignment of values to the three dimensions.
It is still a further object of this invention to monitor the interpretation of incoming natural language for plausibility and expectedness. The goal of this monitoring is to ensure that the interpretation of a natural language clause is likely to be correct. The interpretation of incoming natural language is biased by ordering the components to be selected by a process to be the most likely first given the context, and secondarily the most likely first from experience and knowledge. If the plausibility or expectedness of an interpretation of a natural language input falls below a threshold, the interpretation can be checked for alternate interpretations. An alternate interpretation is tried to find the intended meaning of the statement, i.e., the most plausible and expected interpretation. However, a specific application of the invention can make all possible interpretations, reject the implausible interpretations, and select the most plausible interpretation as determined by the application for example.
It is still a further object of this invention to perform additional storage or retrieval of experience or knowledge to accomplish the objectives of an application implemented with the invention. These additional accesses could also be used to perform operations to accomplish the objectives of the invention. Such operations could include but are not limited to: finding experience or knowledge stored internally; finding experience or knowledge stored externally; communicating with external computer programs; solving problems; evaluating a situation; hypothesizing a situation; determining criteria for evaluating a situation; performing mathematical calculations including numerical, logical, symbolic, geometric, and/or probabilistic; performing simulations; performing calculations in association with an external computer program.
It is still a further object of this invention to make the storage or retrieval of knowledge or experience an interactive process initiated by the invention when certain situations occur during storage or retrieval. Such situations include: failure to address experience or knowledge; addressing experience or knowledge which contradicts the context or previously stored knowledge or experience, e.g., one or more states have two or more values at the same time, or purpose relations which are not consistent; addressing experience or knowledge with an unexpectedness or with a plausibility which falls below a threshold; receiving directives which are inappropriate, disadvantageous, and/or lead to inefficient or suboptimal situations. When such a situation occurs, the invention generates a clarifying question or other appropriate statement indicating the problematic situation. Such output of the invention is intended to ensure proper communication.
It is a further object of this invention to generate text such as for a communication selected by an application of the invention. This text can describe any stored experience or knowledge, or experience or knowledge provided by the application.
It is still a further object of this invention to provide in a communication which is a response to a question or assignment, experience or knowledge during output which is at a level which is adjusted for the receiver. The output content is adjusted in two dimensions. One dimension, the specificity dimension, is the level of detail and varies from general to specific. The other dimension of output content, the explanation dimension, is the degree of explanation and varies from no explanation up to all that is known about the output content. The specificity dimension is set to match the level of the question or assignment. The explanation dimension is set to a level which provides explanation from a typical level of experience or knowledge up to and including the answer or assignment experience or knowledge. The explanation level of experience or knowledge is adjusted according to one or more factors including: the level of the requested experience or knowledge; requests for greater or lesser explanation; the previous history of interacting with the requester; anticipation of potential pitfalls or problems.
It is a further aspect of this invention that the above objects may be performed in a different order because a different ordering is advantageous to an application. Also, backtracking to a previous step may be required when an inconsistency, implausibility or other possible interpretation error is detected.
It is still a further object of this invention to provide methods for teaching the invention experience and knowledge. One method is to directly fill in the storage structures of the invention. Another method is to express the experience or knowledge to be stored possibly with interactive communication with the invention. Another method is specific interfaces for being taught which include: finding the most similar situation to the one being taught; presenting an interface to indicate the experience and knowledge stored for the similar situation with aids to describe the new experience and knowledge in terms of the previously stored experience and knowledge.
If is a further object of the invention to provide learning by the invention with an application of the invention. A learning application can be accomplished directly by storing the text presented to the invention. Often times, such input is incomplete and requires filing in the details between input statements. The application of the invention can attempt to fill in the details with Purpose Identification Method 140. The details can also be filled in by first generalizing related examples, and then determining if the generalization provides a consistent explanation of the details between input statements. In this context xe2x80x9cexplanationxe2x80x9d means a set of clauses which fills in the missing details. A learning application can also be accomplished with a generalized method specific to a storage structure of the invention which asks questions to obtain missing information generally stored in the associated storage structure. The questions and the type of questions are specific to the experience or knowledge to be learned.
In accordance with these and other objects, features and advantages, the invention provides methods and apparatus to take as input natural language text or an equivalent non-textual natural language representation and selects word sense numbers which have associated locations which contain the stored state representation and any stored experience and knowledge all of which either matches a specific occurrence or situation corresponding to the input or which matches the input with some degree of generalization of the input. An input clause is then understood in terms of previously stored knowledge and experience by finding paths in knowledge and experience memory to the locations established in the context of the conversation. Such paths include process paths which are performed to realize the state representation of an input. Such paths also include purpose paths which contain any stored information related to the input location and the context of the conversation and other related experience and knowledge. Such paths can include predictions of what can occur in the future of the situation of the conversation. This method thereby achieves an understanding of the input in terms of stored experience or knowledge. After achieving understanding, the next step depends upon the application of the invention and the situation within the application. Applications include: just-in-time training, tutoring, problem solving, collective memory (the combined experience and knowledge of a group on one or more subjects), exact text search possibly combined with inexact methods such as keyword search, a special purpose interface into a computer system, diagnosing malfunctions, etc. The general process for implementing an application of the invention is to understand an input, perform processing related to the input, generate a communication related to the input as needed, and/or generate apparatus controlling output as needed.